public class Solution2 {
    public int reversePairs(int[] record) {
        //归并排序
        int[] tmpArr = new int[record.length];
        return mergeSort(record, 0, record.length - 1, tmpArr);
    }
    private int mergeSort(int[] nums, int left, int right, int[] tmpArr){
        if(left >= right) return 0;
        int mid = (left + right) / 2;
        int l = mergeSort(nums, left, mid, tmpArr);
        int r = mergeSort(nums, mid + 1, right, tmpArr);
        int ret = merge(nums, left, mid, right, tmpArr);
        return l + r + ret;
    }
    private int merge(int[] nums, int left, int mid, int right, int[] tmpArr){
        int s1 = left;
        int s2 = mid + 1;
        int cur = 0;
        int ret = 0;
        //合并两个有序数组 - 降序合并
        while(s1 <= mid && s2 <= right){
            if(nums[s1] > nums[s2]){
                tmpArr[cur++] = nums[s1++];
                ret += (right - s2 + 1);
            }else{
                tmpArr[cur++] = nums[s2++];
            }
        }
        while(s1 <= mid){
            tmpArr[cur++] = nums[s1++];
        }
        while(s2 <= right){
            tmpArr[cur++] = nums[s2++];
        }
        for(int i = left; i <= right; i++){
            nums[i] = tmpArr[i - left];
        }
        return ret;
    }
}
